#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>

using namespace std;

// 跳跃游戏II
class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int n = nums.size();
        // dp[i]:表示从0到i位置的最少跳跃次数
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        // nums[j] + j >= i dp[i] = dp[j] + 1
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] + j >= i)
                {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[n - 1];
    }
};

class Solution
{
public:
    int jump(vector<int> &nums)
    {
        int n = nums.size();
        int left = 0, right = 0, maxpos = 0, ans = 0;
        while (right < n)
        {
            if (right >= n - 1)
                return ans;
            for (int i = left; i <= right; i++)
            {
                maxpos = max(maxpos, nums[i] + i);
            }
            left = right + 1;
            right = maxpos;
            ans++;
        }

        return ans;
    }
};

// 跳跃游戏
class Solution
{
public:
    bool canJump(vector<int> &nums)
    {
        int n = nums.size();
        int left = 0, right = 0, maxpos = 0;
        while (left <= right)
        {
            if (maxpos >= n - 1)
                return true;
            for (int i = left; i <= right; i++)
            {
                maxpos = max(maxpos, nums[i] + i);
            }
            left = right + 1;
            right = maxpos;
        }

        return false;
    }
};

// 划分字母区间
class Solution
{
public:
    vector<int> partitionLabels(string s)
    {
        int last[26];
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            last[s[i] - 'a'] = i;
        }
        vector<int> ans;
        int start = 0, end = 0;
        for (int i = 0; i < n; i++)
        {
            // 前面字母能跳到的最远距离
            end = max(end, last[s[i] - 'a']);
            if (i == end)
            {
                ans.push_back(end - start + 1);
                start = end + 1;
            }
        }

        return ans;
    }
};

// 只出现一次的数字
class Solution
{
public:
    int singleNumber(vector<int> &nums)
    {
        int ans = 0;
        for (auto x : nums)
            ans ^= x;
        return ans;
    }
};

// 颜色分类
class Solution
{
public:
    void sortColors(vector<int> &nums)
    {
        int i = 0, left = -1, right = nums.size();
        while (i < right)
        {
            // [0,left] -- 0
            // [left + 1,right - 1] -- 1
            // [right,n - 1] -- 2
            if (nums[i] == 0)
                std::swap(nums[++left], nums[i++]);
            else if (nums[i] == 1)
                i++;
            else
                std::swap(nums[i], nums[--right]);
        }
    }
};

// LRU缓存
class LRUCache
{
private:
    typedef list<pair<int, int>>::iterator iter;
    list<pair<int, int>> _LRUList;
    unordered_map<int, iter> _hashMap;
    int _capacity;

public:
    LRUCache(int capacity)
    {
        _capacity = capacity;
    }

    int get(int key)
    {
        auto ret = _hashMap.find(key);
        if (ret == _hashMap.end())
            return -1;

        iter it = ret->second;
        _LRUList.splice(_LRUList.begin(), _LRUList, it);
        return it->second;
    }

    void put(int key, int value)
    {
        auto ret = _hashMap.find(key);
        if (ret != _hashMap.end())
        {
            iter it = ret->second;
            it->second = value;

            _LRUList.splice(_LRUList.begin(), _LRUList, it);
        }
        else
        {
            if (_capacity == _hashMap.size())
            {
                pair<int, int> back = _LRUList.back();
                _hashMap.erase(back.first);
                _LRUList.pop_back();
            }

            _LRUList.push_front(make_pair(key, value));
            _hashMap[key] = _LRUList.begin();
        }
    }
};
